﻿#pragma once
#include "FormatedUtil.h"
#include "Index.h"

class IMaxestMultiOfSubArr
{
public:
	/**
	 * 连续子数组的最大乘积.
	 * https://www.nowcoder.com/practice/fd8c819c07c9493887bfac8549c119f4?tpId=230&tags=&title=&difficulty=0&judgeStatus=0&rp=0&sourceUrl=%2Fexam%2Foj%3Fpage%3D1%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D230
	 *
	 * 描述
	 * 输入一个长度为 n 的整型数组 nums，数组中的一个或连续多个整数组成一个子数组。求所有子数组的乘积的最大值。
	 * 1.子数组是连续的，且最小长度为 1 ，最大长度为 n
	 * 2.长度为 1 的子数组，乘积视为其本身，比如 [4] 的乘积为 4
	 * 3.该题的数据保证最大的乘积不会超过 int 的范围
	 */
	virtual int maxestMultiOfSubArr(std::vector<int>&arr) = 0;
};
class MaxestMultiOfSubArr
{
public:
	class DP:public IMaxestMultiOfSubArr
	{
	public:
		int maxestMultiOfSubArr(std::vector<int>& arr) override
		{
			if (arr.empty())
				return 0;

			int maxestMulti = arr[0];
			int dp_min = arr[0], dp_max = arr[0];

			const int arrSize = arr.size();
			for (int i = 1; i < arrSize; ++i)
			{
				const int next_dp_min = std::min<>({ dp_min * arr[i], dp_max * arr[i],arr[i] });
				const int next_dp_max = dp_max = std::max<>({ dp_min * arr[i], dp_max * arr[i],arr[i] });

				dp_min = next_dp_min;
				dp_max = next_dp_max;
				maxestMulti = std::max<>(dp_max, maxestMulti);
			}
			return maxestMulti;
		}
	};
};

